package com.company.math;

/**
 * @author jrue
 * @description https://leetcode-cn.com/problems/integer-break/
 * 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
 * @date 2019/11/14 10:22
 */
public class IntegerBreak {
    public static void main(String[] args) {
        System.out.println(integerBreak(10));
    }

    public static int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for (int i = 3; i < n + 1; i++) {
            int max = 0;
            for (int j = 1; j < i / 2 + 1; j++) {
                int num01 = j;
                int num02 = i - j;
                if (num01 < dp[j]) {
                    num01 = dp[j];
                }
                if (num02 < dp[num02]) {
                    num02 = dp[num02];
                }
                if (num01 * num02 > max) max = num01 * num02;
            }
            dp[i] = max;
        }
        return dp[n];
    }
}
